package com.base.dataStructure.recurrence;

/**
 * @Author: hdhao
 * @Create: 2023/3/29 - 20:43
 * @Version: v1.0
 */
//杨辉三角
public class PaascalTriangle {
    public static void main(String[] args) {
        print1(5);
        System.out.println();
        print2(5);
        System.out.println();
        print3(5);
    }
    //----------------------记忆法改进杨辉三角实现-------------------------------------
    public static void print2(int n){
        int[][] triangle = new int[n][];
        for (int i = 0;i<n;i++){
            triangle[i] = new int[i+1];
            printSpace(n,i);
            for (int j = 0; j<=i;j++){
                System.out.printf("%-4d",element2(triangle,i,j));
            }
            System.out.println();
        }
    }

    private static int element2(int[][] triangle, int i, int j){
        if (triangle[i][j] > 0){
            return triangle[i][j];
        }
        if (j == 0 || i == j){
            triangle[i][j] = 1;
            return 1;
        }
        triangle[i][j] = element2(triangle,i-1,j-1)+element2(triangle,i-1,j);
        return triangle[i][j];
    }
    //----------------------杨辉三角实现---------------------------------------------------
    private static int element1(int i,int j){
        if (j == 0 || i == j){
            return 1;
        }
        return element1(i-1,j-1)+element1(i-1,j);
    }

    private static void printSpace(int n,int i){
        int num = (n-1-i)*2;
        for (int j = 0; j<num;j++){
            System.out.print(" ");
        }
    }
    public static void print1(int n){
        for (int i = 0;i<n;i++){
            printSpace(n,i);
            for (int j = 0; j<=i;j++){
                System.out.printf("%-4d",element1(i,j));
            }
            System.out.println();
        }
    }
    //------------------------使用一维数组优化记忆法-----------------------------
    private static void createRow(int[] row ,int i){
        if (i == 0){
            row[0]= 1;
            return;
        }
        for (int j = i; j > 0;j--){
            row[j] = row[j]+row[j-1];
        }
    }

    public static void print3(int n){
        int[] row = new int[n];
        for (int i = 0;i<n;i++){
            createRow(row,i);
            printSpace(n,i);
            for (int j = 0; j<=i;j++){
                System.out.printf("%-4d",row[j]);
            }
            System.out.println();
        }
    }
}
